#include <iostream>

using namespace std;

/*
Reverse a binary tree. If the node is left child for parent, 
then convert its right child to its parent, and left child to NULL. 
If the node is right child for parent, convert its left child to 
its parent and right child to NULL. After revert, the tree becomes a graph. 

Followup question, how to reverse the tree through non-recursive routine
*/

class TreeNode
{
public:
	int Data;
	class TreeNode *lChild;
	class TreeNode *rChild;
};

TreeNode *CreateBT( int *Array, int start, int end )
{
	//
	// Assume the Array is ordered so the new
	// created BT should be BST
	//
	if( start > end )
		return NULL;

	int middle  = start + (end-start)/2; //avoid integer overflow
	TreeNode * node = new TreeNode();
	
	node->Data = Array[middle];
    node->lChild = CreateBT( Array, start, middle-1 );
    node->rChild = CreateBT( Array, middle+1, end );

	return node;
}

void
DeleteBT( TreeNode* root )
{
	if( !root )
		return;
	DeleteBT( root->lChild );
	DeleteBT( root->rChild );

	delete root;
}

TreeNode *ReverseTree( TreeNode *root)
{
	TreeNode* left = NULL;
	TreeNode* right = NULL;

	if( !root )
		return NULL;

	if( root->lChild )
	{
		left = ReverseTree( root->lChild );
		left->rChild = root;
		left->lChild = NULL;
	}

	if( root->rChild )
	{
		right = ReverseTree( root->rChild );
		right->lChild = root;
		right->rChild = NULL;
	}

	return root;
}

int main()
{
	int Array[10] = {1,2,3,4,5,6,7,8,9,10};
	TreeNode *root = CreateBT(Array, 0, 9);

	ReverseTree( root );

	// need to free the trees
	cout<<"Press anykey to terminate..."<<endl;
	return getchar();
}